//
//  Problem309.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 309. 最佳买卖股票时机含冷冻期 【动态规划】【股票】
 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
 
 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 示例:

 输入: [1,2,3,0,2]
 输出: 3
 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 */
@objcMembers class Problem309: NSObject {
    func solution() {
        print(maxProfitClearAlloc([1,2,3,0,2]))
        print(maxProfitClearAlloc([1000,12,13,5,2,100,2]))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[len][2]
     2: dp[i][0] 持有i这个股票, 获得的最大值
        dp[i][1] 不持有i这个股票, 获得的最大值
     3: dp[i][0]: 手里有股票，所有有2种情况：max()
            本次购买： 因为有冷冻期1天，必须是i-2天没有持股时购买 = dp[i-2][1] - prices[i]
            本次不购买：= dp[i-1][0]： 上次购买了，不变
        dp[i][1]: 手里没股票，有2种情况
            本次卖了：dp[i-1][0] + prices[i]
            本次不处理：= dp[i-1][1]
     */
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: 2), count: prices.count+1)
        dp[0][0] = Int.min
        dp[0][1] = 0
        dp[1][0] = -prices[0]
        dp[1][1] = 0
        for i in 2...prices.count {
            if dp[i-2][1] == Int.min {
                dp[i][0] = dp[i-1][0]
            } else {
                dp[i][0] = max(dp[i-2][1] - prices[i-1], dp[i-1][0])
            }
            dp[i][1] = max(dp[i-1][0] + prices[i-1], dp[i-1][1])
        }
        
        return dp.last?.last ?? 0
    }
    
    /*
     优化
     dp[i][0]只与 dp[i-2][1] dp[i-1][0] 有关
     dp[i][1]只与 dp[i-1][0] dp[i-1][1] 有关
     */
    func maxProfitClearAlloc(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }
        
        var lastlast1 = 0
        var last0 = -prices[0]
        var last1  = 0
        for i in 2...prices.count {
            last0 = max(lastlast1 - prices[i-1], last0)
            
            lastlast1 = last1
            last1 = max(last0 + prices[i-1], last1)
        }
        
        return last1
    }
}
